import java.util.*;

/**
 * 题目：素数之积
 * 
 * 题目描述：
 * RSA加密算法依赖于大整数分解的困难性。给定一个32位正整数，进行素数分解，
 * 找到两个素数，使得它们的乘积等于给定的整数。
 * 
 * 输入描述：
 * 一个正整数num，0 < num <= 2147483647
 * 
 * 输出描述：
 * 如果成功找到两个素数，输出这两个素数，用单个空格分隔，按升序排列（从小到大）。
 * 如果分解失败（即找不到这样的两个素数），输出-1 -1。
 * 
 * 示例1：
 * 输入：15
 * 输出：3 5
 * 
 * 示例2：
 * 输入：27
 * 输出：-1 -1
 * 
 * 解题思路：
 * 这是一个素数分解问题，需要找到两个素数使得它们的乘积等于给定的数。
 * 
 * 算法分析：
 * - 时间复杂度：O(√n) 对于试除法
 * - 空间复杂度：O(1)
 * - 算法类型：数论，素数分解
 */
public class PrimeFactorization {
    
    /**
     * 方法1：试除法（推荐使用）
     * 使用试除法找到两个素数因子
     * 
     * 算法思路：
     * 1. 从2开始试除，直到√num
     * 2. 如果找到因子i，检查i和num/i是否都是素数
     * 3. 如果都是素数，返回这两个数
     * 
     * 时间复杂度：O(√n)
     * 空间复杂度：O(1)
     */
    public static int[] findTwoPrimes1(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                int factor1 = i;
                int factor2 = num / i;
                if (isPrime(factor1) && isPrime(factor2)) {
                    return new int[]{Math.min(factor1, factor2), Math.max(factor1, factor2)};
                }
            }
        }
        return new int[]{-1, -1};
    }
    
    /**
     * 方法2：埃拉托斯特尼筛法
     * 使用筛法预计算素数，然后查找因子
     * 
     * 算法思路：
     * 1. 使用埃拉托斯特尼筛法预计算所有素数
     * 2. 遍历素数列表，查找因子
     * 3. 检查对应的另一个因子是否也是素数
     * 
     * 时间复杂度：O(n log log n)
     * 空间复杂度：O(n)
     */
    public static int[] findTwoPrimes2(int num) {
        boolean[] isPrime = sieveOfEratosthenes(num);
        
        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i] && num % i == 0) {
                int factor2 = num / i;
                if (factor2 <= num && isPrime[factor2]) {
                    return new int[]{i, factor2};
                }
            }
        }
        return new int[]{-1, -1};
    }
    
    /**
     * 方法3：优化试除法
     * 使用优化的试除法，跳过偶数
     * 
     * 算法思路：
     * 1. 先检查2是否为因子
     * 2. 然后只检查奇数因子
     * 3. 减少不必要的计算
     * 
     * 时间复杂度：O(√n)
     * 空间复杂度：O(1)
     */
    public static int[] findTwoPrimes3(int num) {
        // 检查2是否为因子
        if (num % 2 == 0) {
            int factor2 = num / 2;
            if (isPrime(factor2)) {
                return new int[]{2, factor2};
            }
        }
        
        // 检查奇数因子
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                int factor1 = i;
                int factor2 = num / i;
                if (isPrime(factor1) && isPrime(factor2)) {
                    return new int[]{Math.min(factor1, factor2), Math.max(factor1, factor2)};
                }
            }
        }
        return new int[]{-1, -1};
    }
    
    /**
     * 方法4：米勒-拉宾素性测试
     * 使用概率性素性测试算法
     * 
     * 算法思路：
     * 1. 使用米勒-拉宾算法进行素性测试
     * 2. 对于大数，比确定性算法更快
     * 3. 有一定的错误概率，但可以控制
     * 
     * 时间复杂度：O(k log³n)
     * 空间复杂度：O(1)
     */
    public static int[] findTwoPrimes4(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                int factor1 = i;
                int factor2 = num / i;
                if (millerRabinTest(factor1) && millerRabinTest(factor2)) {
                    return new int[]{Math.min(factor1, factor2), Math.max(factor1, factor2)};
                }
            }
        }
        return new int[]{-1, -1};
    }
    
    /**
     * 方法5：费马小定理法
     * 使用费马小定理进行素性测试
     * 
     * 算法思路：
     * 1. 使用费马小定理进行素性测试
     * 2. 对于某些数，比试除法更快
     * 3. 有一定的错误概率
     * 
     * 时间复杂度：O(k log n)
     * 空间复杂度：O(1)
     */
    public static int[] findTwoPrimes5(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                int factor1 = i;
                int factor2 = num / i;
                if (fermatTest(factor1) && fermatTest(factor2)) {
                    return new int[]{Math.min(factor1, factor2), Math.max(factor1, factor2)};
                }
            }
        }
        return new int[]{-1, -1};
    }
    
    /**
     * 判断一个数是否为素数（试除法）
     */
    private static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    /**
     * 埃拉托斯特尼筛法
     */
    private static boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime;
    }
    
    /**
     * 米勒-拉宾素性测试
     */
    private static boolean millerRabinTest(int n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;
        
        int d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }
        
        // 使用几个小的底数进行测试
        int[] bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        
        for (int a : bases) {
            if (a >= n) continue;
            
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1) continue;
            
            boolean composite = true;
            for (int j = 0; j < s - 1; j++) {
                x = (x * x) % n;
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            
            if (composite) return false;
        }
        
        return true;
    }
    
    /**
     * 费马小定理素性测试
     */
    private static boolean fermatTest(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        
        // 使用几个小的底数进行测试
        int[] bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        
        for (int a : bases) {
            if (a >= n) continue;
            if (modPow(a, n - 1, n) != 1) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 快速幂取模
     */
    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            exp >>= 1;
            base = (base * base) % mod;
        }
        
        return result;
    }
    
    /**
     * 主方法 - 程序入口
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        System.out.println("请输入一个正整数num：");
        int num = scanner.nextInt();
        
        // 测试所有方法
        System.out.println("\n=== 所有算法结果对比 ===");
        
        int[] result1 = findTwoPrimes1(num);
        int[] result2 = findTwoPrimes2(num);
        int[] result3 = findTwoPrimes3(num);
        int[] result4 = findTwoPrimes4(num);
        int[] result5 = findTwoPrimes5(num);
        
        System.out.println("方法1（试除法）: " + result1[0] + " " + result1[1]);
        System.out.println("方法2（埃拉托斯特尼筛法）: " + result2[0] + " " + result2[1]);
        System.out.println("方法3（优化试除法）: " + result3[0] + " " + result3[1]);
        System.out.println("方法4（米勒-拉宾素性测试）: " + result4[0] + " " + result4[1]);
        System.out.println("方法5（费马小定理法）: " + result5[0] + " " + result5[1]);
        
        // 验证结果
        System.out.println("\n=== 结果验证 ===");
        if (result1[0] != -1) {
            System.out.println("验证: " + result1[0] + " * " + result1[1] + " = " + (result1[0] * result1[1]));
        }
        
        // 推荐使用的方法
        System.out.println("\n推荐使用方法1（试除法），对于32位整数效率最高且结果准确");
        
        scanner.close();
    }
}
